package 程序员面试金典;

/**
 * 面试题 02.02. 返回倒数第 k 个节点
 * 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
 *
 * 注意：本题相对原题稍作改动
 *
 * 示例：
 *
 * 输入： 1->2->3->4->5 和 k = 2
 * 输出： 4
 * 说明：
 *
 * 给定的 k 保证是有效的。
 */
public class T02_02 {
    public int kthToLast(ListNode head, int k) {

        //使用两个指针 前指针先走k-1步 然后后指针再出发 直到前指针到最后一个节点 此时后指针指向的就时倒数第K个节点

        ListNode first = head;
        ListNode second = head;

        for (int i = 0; i <k; i++) {
            first = first.next;
        }

        while (first!=null){
            first = first.next;
            second = second.next;
        }

        return second.val;

    }

    //链表的定义
    static class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
}
